Link to this headingLinear Congruent Generator (LCG)

  • Using about 6 sequential outputs you can generate all of the parameters and sync the state

Link to this headingImplementation

import math, functools def findmodulus(outputs): temp = [] for idx in range(0, len(outputs)-1): temp.append(outputs[idx+1] - outputs[idx]) temp2 = [] for idx in range(0, len(temp)-2): temp2.append(abs((temp[idx+2] * temp[idx]) - temp[idx+1]**2)) return functools.reduce(math.gcd, temp2) def findmult(x0, x1, x2, mod): temp = x1 - x2 temp2 = pow(x0 - x1, -1, mod) return (temp * temp2) % mod def findinc(x0, x1, a, mod): # x1 = x0*a + b # x1 - (x0*a) = b return (x1 - (x0 * a)) % mod def findperoid(lcg): first = lcg.next() counter = 0 while first != lcg.next(): counter +=1 if counter % 0xFFFFFF == 0: print(counter) print(f"Found Period: {counter}") class LCG(object): """docstring for LCG""" def __init__(self, seed=1337, a=1103515245, b=12345, c=0x7FFFFFFF): super(LCG, self).__init__() self.state = seed self.a = a self.b = b self.c = c def next(self): # seed = (seed * A + B) % C self.state = (self.state * self.a + self.b) % self.c return self.state def int_32(self, number): return int(0xFFFFFFFF & number) if __name__ == '__main__': lcg = LCG() #### Computing the Paramaters seeds = [] for _ in range(10): seeds.append(lcg.next()) #Recover Mod found_mod = findmodulus(seeds) print(f"Mod: {found_mod}") #Recover Mult a found_a = findmult(seeds[0], seeds[1], seeds[2], found_mod) print(f"A: {found_a}") #Recover add b found_b = findinc(seeds[0], seeds[1], found_a, found_mod) print(f"B: {found_b}") assert found_mod == lcg.c assert found_a == lcg.a assert found_b == lcg.b

Link to this headingAttacks

Predicting values from a Linear Congruential Generator
Cracking a linear congruential generator